use crate::solution::Solution;
use crate::data_structure::list_node::ListNode;

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    // 单调栈
    pub fn next_larger_nodes(mut head: Option<Box<ListNode>>) -> Vec<i32> {
        use std::collections::VecDeque;
        let (mut node, mut queue) = (vec![], VecDeque::new());
        while head.is_some() {
            node.push(head.as_ref().unwrap().val);
            head = head.unwrap().next.take();
        }
        let mut ret = vec![0; node.len()];
        for i in 0..node.len() {
            while !queue.is_empty() && node[queue[queue.len() - 1] as usize] < node[i] { ret[queue.pop_back().unwrap() as usize] = node[i]; }
            queue.push_back(i as i32);
        }
        ret
    }

}

#[cfg(test)]
mod tests {
    // use super::*;
    // 不要引入util里的ListNode,报错！
    // use crate::util::list_node_use::ListNode;
    use crate::data_structure::list_node::ListNode;
    use crate::solution::Solution;

    #[test]
    fn test_1() {
        let vec = vec![2,1,5];
        let list_node = ListNode::vec1d_to_list_node(vec);
        println!("{:?}", list_node);
        let expected = vec![5,5,0];

        let ans = Solution::next_larger_nodes(list_node);
        println!("ans: {:?}", ans);

        assert_eq!(ans, expected);
    }

    #[test]
    fn test_2() {
        let vec = vec![2,7,4,3,5];
        let list_node = ListNode::vec1d_to_list_node(vec);
        println!("{:?}", list_node);
        let expected = vec![7,0,5,5,0];

        let ans = Solution::next_larger_nodes(list_node);
        println!("ans: {:?}", ans);

        assert_eq!(ans, expected);
    }
}